1. Field of the Invention
The present invention relates to error checking codes. More specifically, the techniques of the present invention provide mechanisms for efficiently computing error checking codes such as cyclic redundancy checks (CRCs).
2. Description of Related Art
Error checking codes such as cyclic redundancy checks (CRCs) are used in many communication and storage applications to detect data corruption. In a typical example, a message (M) is divided by a polynomial (P) known to both a sender and a receiver. The remainder (R) is transmitted with the message (M) to the receiver. The receiver uses the remainder (R) to verify that the message (M) has not been corrupted. R is referred to also as the Frame Check Sequence (FCS) or as a CRC. Although it is possible that different messages can give the same remainder R when divided by a polynomial (P), CRC computations have been highly effective, as the probability that corrupted data can pass a 32 bit CRC (CRC32) check is remote.
Galois field division is often used to determine R. Galois field division is implemented using shift registers and exclusive-OR (XOR) gates. In a simplified example, division can be performed by performing one XOR, bit shifting, performing another XOR, bit shifting, etc. However, computation of CRCs remains resource intensive. Wide bit width CRC require a large amount of logic or circuitry for computation. Some mechanisms allow parallel computation of CRCs. However, available mechanisms treat the entire CRC as a single unit and still require many levels of logic.
Performing CRCs computations can be inefficient on a variety of devices. That is, performing these computations may require many levels of logic or require a large amount of resources. Consequently, the techniques of the present invention provide improved mechanisms for computing error checking codes such as CRCs.